package core;

public class HeapSorter
{

	/**
	 * The data to be sorted
	 */
	private Node[] a;

	/**
	 * The size of the data
	 */
	private int size;

	public HeapSorter(Node[] nodes)
	{
		a = nodes;
		size = a.length;
	}

	public void buildheap()
	{
		// heapify the elements second part of the array
		for (int v = size / 2 - 1; v >= 0; v--)
			heapify(v);
	}

	public void heapify(int v)
	{
		int w = 2 * v + 1; // first descendant of v
		while (w < size) {
			if (w + 1 < size) // is there a second descendant?
				if (a[w + 1].compareTo(a[w]) < 0)
					w++;
			// w is the descendant of v with maximum label

			if (a[v].compareTo(a[w]) <= 0)
				return; // v has heap property
			// otherwise
			exchange(v, w); // exchange labels of v and w
			v = w; // continue
			w = 2 * v + 1;
		}
	}

	public void otherHeapify(int i)
	{
		int v = i;
		int w = i + 1; // first descendant of v
		while (w < size)
		{
			if (w + 1 < size) // is there a second descendant?
				if (a[w + 1].compareTo(a[w]) < 0)
					w++;
			// w is the descendant of v with maximum label

			if (a[v].compareTo(a[w]) <= 0)
				return; // v has heap property
			// otherwise
			exchange(v, w); // exchange labels of v and w
			v = w; // continue
			w = 2*v + 1 - i;
		}
	}

	private void exchange(int i, int j)
	{
		Node t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
}